package com.example.demo.arithmetic.algorithm.greedy.activity_selection;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class ActivitySelectionProblem {

    static class Activity {
        // 活动开始时间
        int start;
        // 活动结束时间
        int end;
        int index;

        public Activity(int index, int start, int end) {
            this.index = index;
            this.start = start;
            this.end = end;
        }

        @Override
        public String toString() {
            return "Activity{" +
                    "index=" + index +
                    '}';
        }
    }

    public static void main(String[] args) {
        Activity[] activities = {
                new Activity(0, 1, 3),
                new Activity(1, 2, 5),
                new Activity(2, 4, 6),
                new Activity(3, 6, 8),
                new Activity(4, 5, 7),
                new Activity(5, 8, 9)
        };

        int maxActivities = selectMaxActivities(activities, activities.length);
        System.out.println("最大可选活动数: " + maxActivities);
    }

    private static int selectMaxActivities(Activity[] activities, int n) {
        // 最先结束时间进行排序
        Arrays.sort(activities, Comparator.comparingInt(a -> a.end));
        List<Activity> result = new ArrayList<>();
        Activity prev = activities[0];
        result.add(prev);
        //int count = 1;
        int lastEndTime = prev.end;
        for (int i = 1; i < activities.length; i++) {
            Activity curr = activities[i];
            if (curr.start >= lastEndTime) {
                //                count++;
                result.add(curr);
                lastEndTime = curr.end;
            }
        }
        return result.size();
    }
}
